package br.ufrgs.ga;

import java.util.LinkedList;
import java.util.List;
import java.util.Random;

import br.ufrgs.ga.exceptions.AlgorithmException;
import br.ufrgs.ga.fitness.FitnessCalculator;
import br.ufrgs.ga.listeners.GenerationCreatedListener;
import br.ufrgs.ga.listeners.GenerationInformation;
import br.ufrgs.ga.model.IChromosome;
import br.ufrgs.ga.model.Individual;
import br.ufrgs.ga.model.Population;

/**
 * Abstracts a genetic algorithm implementation.
 * @author mineiro
 *
 */
public abstract class GeneticAlgorithm {

	/**
	 * Max number of generations that the algorithm will run until a valid solution is find.
	 */
	public static final int MAX_GENERATION = 100;
	
	/**
	 * Listeners that will be notified when a new generation is created.
	 */
	private List<GenerationCreatedListener> listeners = new LinkedList<GenerationCreatedListener>();
	
	/**
	 * Chromosome fitness calculator.
	 */
	protected FitnessCalculator fitnessCalculator;
	
	/**
	 * Population.
	 */
	protected Population population;
	
	/**
	 * The chromosome with the best fitness found so far.
	 */
	protected Individual bestIndividualSoFar;
	
	/**
	 * List of selected chromosomes to reproduction.
	 */
	protected List<Individual> selectedParentsToReproduction = new LinkedList<Individual>();

	/**
	 * Executes the algorithm.
	 * @throws AlgorithmException thrown if anything bad happens.
	 */
	public void execute() throws AlgorithmException {
		try {
			initializePopulation();
			
			// Initial generation value
			int generation = 1;
			
			// notify all generation listeners that a new generation has been created and
			// give then all useful generation information.
			notifyGenerationListeners(new GenerationInformation(generation, bestIndividualSoFar));
			
			// The algorithm stop condition
			while(!solutionFound() && generation < MAX_GENERATION) {				
				fitnessCalculation();
				selectParentsToReproduction();
				reproduction();
				mutation();
				
				// next generation...
				generation++;
				
				// notify all generation listeners that a new generation has been created and
				// give then all useful generation information.
				notifyGenerationListeners(new GenerationInformation(generation, bestIndividualSoFar));
			}
		} catch (Exception e) {
			throw new AlgorithmException("An exception has occured when the algorithm was running.", e);
		}
	}
	
	/**
	 * initializes the initial population. Generally it is a random initialization. 
	 */
	public abstract void initializePopulation();
	
	/**
	 * Verify the stop condition of the algorithm.
	 * @return true if the stop condition is reached, false otherwise.
	 */
	public abstract boolean solutionFound();
	
	/**
	 * Calculates the fitness of all population elements and selects the best one.
	 */
	public void fitnessCalculation() {
		Individual mostAdaptedIndividualAtCurrentPopulation = population.getMostAdaptedIndividual();
		if (mostAdaptedIndividualAtCurrentPopulation.getFitnessValue() > this.bestIndividualSoFar.getFitnessValue()) {
			System.out.println("A better solution was found...\nOld solution: " + mostAdaptedIndividualAtCurrentPopulation + "\nNew solution: " + bestIndividualSoFar);
			this.bestIndividualSoFar = mostAdaptedIndividualAtCurrentPopulation;
		}
	}

	/**
	 * Selects some population elements to reproduction and possibly generate better elements.
	 */
	public void selectParentsToReproduction() {
		this.selectedParentsToReproduction = population.getSubListOfWorstIndivuduals(Population.REPRODUCTION_FREQUENCE);
	}
	
	/**
	 * Reproduction of the selected elements at {@link IGeneticAlgorithm#selectParentsToReproduction()}.
	 */
	public void reproduction() {
		Population newPopulation = new Population();
		for(int i = 1; i < selectedParentsToReproduction.size(); i++) {
			IChromosome<String> child = selectedParentsToReproduction.get(i).getChromosome().reproduce(selectedParentsToReproduction.get(i - 1).getChromosome());
			Individual newIndividual = new Individual(child, fitnessCalculator);
			newPopulation.add(newIndividual);
		}
		newPopulation.addAll(population.getSubListOfBestIndivuduals(Population.REPRODUCTION_FREQUENCE - 1));
		this.population = newPopulation;
	}
	
	/**
	 * Mutate some population elements in attempt to increase variability of population.
	 * This operation generally is implemented as a random operation.
	 */
	public void mutation() {
		Random rand = new Random(System.currentTimeMillis());
		for (int i = 0; i < Population.MUTATION_FREQUENCE; i++) {
			Individual individual = population.getIndividualAt(rand.nextInt(Population.POPULATION_SIZE));
			individual.getChromosome().mutate();
		}
	}
	
	/**
	 * Returns the best individual found through the generations.
	 * @return the best individual found.
	 */
	public Individual getBestIndividualSoFar() {
		return bestIndividualSoFar;
	}
	
	/**
	 * Returns the population.
	 * @return population.
	 */
	public Population getPopulation() {
		return population;
	}
	
	/**
	 * Returns the selected individuals to reproduction.
	 * @return selected individuals to reproduction
	 */
	public List<Individual> getSelectedIndividualsToReproduction() {
		return this.selectedParentsToReproduction;
	}
	
	/**
	 * Register a listener for the generation creation event.
	 * @param listener object that wants to know about the generation creation event.
	 */
	public void addGenerationListener(GenerationCreatedListener listener) {
		this.listeners.add(listener);
	}
	
	/**
	 * Unregister a listener for the generation creation event.
	 * @param listener the listener to be removed.
	 */
	public void removeGenerationListener(GenerationCreatedListener listener) {
		this.listeners.remove(listener);
	}
	
	/**
	 * Notify all generation listeners about the creation of a new generation.
	 * @param generationInformation
	 */
	public void notifyGenerationListeners(GenerationInformation generationInformation) {
		for(GenerationCreatedListener listener : listeners) {
			listener.generationCreated(generationInformation);
		}
		
		System.out.println("Listeners for generation criation notified...");
	}
}
